#define  _CRT_SECURE_NO_WARNINGS
#include "tree.h"

TreeNode* BuyNewNode(int x)
{
	TreeNode* newnode = (TreeNode*)malloc(sizeof(TreeNode));
	assert(newnode);
	newnode->val = x;
	newnode->left = nullptr;
	newnode->right = nullptr;

	return newnode;
}

void PreOrder(TreeNode* p)
{
	if (p == nullptr)
	{
		return;
	}
	PreOrder(p->left);
	cout << p->val << " ";
	PreOrder(p->right);
}

void InOrder(TreeNode* p)
{
	if (p == nullptr)
	{
		return;
	}
	cout << p->val << " ";
	InOrder(p->left);
	InOrder(p->right);
}

void PostOrder(TreeNode* p)
{
	if (p == nullptr)
	{
		return;
	}
	PostOrder(p->left);
	PostOrder(p->right);
	cout << p->val << " ";
}

int BinaryTreeSize(TreeNode* p)
{
	if (nullptr == p)
	{
		return 0;
	}
	
	return 1 + BinaryTreeSize(p->left) + BinaryTreeSize(p->right);
}

int BinaryTreeLeafSize(TreeNode* p)
{
	if (nullptr == p)
	{
		return 0;
	}
	if (p->left == nullptr && p->right == nullptr)
	{
		return 1;
	}

	return BinaryTreeLeafSize(p->left) + BinaryTreeLeafSize(p->right);
}

int BinaryTreeLevelKSize(TreeNode* p, int k)
{
	if (nullptr == p)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(p->left,k-1) + BinaryTreeLevelKSize(p->right,k-1);
}

int BinaryTreeDepth(TreeNode* p)
{
	if (nullptr == p)
	{
		return 0;
	}
	int leftdep = BinaryTreeDepth(p->left);
	int rightdep = BinaryTreeDepth(p->right);

	return leftdep >= rightdep ? 1+BinaryTreeDepth(p->left) : 1+BinaryTreeDepth(p->right);
}


TreeNode* BinaryTreeFind(TreeNode* p, int x)
{
	if (nullptr == p)
	{
		return nullptr;
	}
	if (p->val == x)
	{
		return p;
	}
	TreeNode* leftfind =  BinaryTreeFind(p->left, x);
	if (leftfind)
	{
		return leftfind;
	}
	TreeNode* rightfind = BinaryTreeFind(p->right, x);
	if (rightfind)
	{
		return rightfind;
	}
	return nullptr;
}